﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0015_StrStr
    {
        // 实现 strStr()

        // 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

        // 说明：
        //  当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
        //  对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

        // 提示：
        //  0 <= haystack.length, needle.length <= 5 * 10^4
        //  haystack 和 needle 仅由小写英文字符组成


        public void Test()
        {
            // abba
            // bbai
            string haystack = "mississippi",
                needle = "issipi";
            Console.WriteLine(StrStr(haystack, needle));
            Console.Read();
        }

        public int StrStr(string haystack, string needle)
        {
            if (needle == "")
                return 0;
            if (needle.Length > haystack.Length)
                return -1;
            int i = 0, j = 0;
            while (i < haystack.Length && i < haystack.Length - needle.Length + 1)
            {
                while (haystack[i + j] == needle[j])
                {
                    if (j == needle.Length - 1)
                    {
                        return i;
                    }
                    j++;
                }
                j = 0;
                i++;
            }
            return -1;
        }
        public int strStr1(string haystack, string needle)
        {
            if (needle.Length == 0)
                return 0;
            int i = 0;
            int j = 0;
            /**
             * 数组next表示pattern指定的下标前具有相同的字符串数量，语言组织能力不好，可能不是太好理解，我举个例子吧
             * ，比如ABCABA，数组next[0]是-1，这个是固定的，因为第一个A前面是没有字符的，next[1]是0，因为B的前面就一个A，没有
             * 重复的，所以是0,同理next[2]也是,next[3]也是0,而next[4]是1，因为next[4]所指向的是第二个B，第二个B前面有一个A和
             * 第一个A相同，所以是1,next[5]是2，因为next[5]所指向的是最后一个Ａ，因为前面的Ａ对比成功，并且Ｂ也对比成功，所以是２，
             * 也就是ＡＢ两个字符串匹配成功,再举个例子，比如WABCABA，数组除了第一个为-1，其他的都是为0，因为只有第一个匹配成功之后
             * 才能匹配后面的，虽然后面的AB和前面的AB匹配成功，但是后面AB的前面是C和前面AB的前面一个W不匹配，所以后面的匹配都是0.
             * 要记住只有指定字符前面的字符和第一个字符匹配成功的时候才能往后匹配，否则后面的永远都是先和第一个匹配。
             */
            int[] next = new int[needle.Length];
            getNext(needle, next);
            while (i < haystack.Length && j < needle.Length)
            {
                /**
                 * 这里j等于-1的时候也只有在下面next数组赋值的时候才会出现，并且只有在数组next[0]的时候才会等于-1，
                 其他时候是没有的，这一点要谨记，待会下面求next数组的时候就会用到。这里可以这样来理解，如果j不等于-1，
                 并且下标i和j所指向的字符相等，那么i和j分别往后移一位继续比较，这个很好理解，那么如果j==-1的时候，就表示
                 就表示前面没有匹配成功的，同时i往后移一位，j置为0（j==-1的时候，j++为0），再从0开始比较。
                 */
                if (j == -1 || haystack[i] == needle[j])
                {
                    i++;
                    j++;
                }
                else
                {
                    /**
                     * i = i - j + 1;
                     j = 0;
                     返回到指定的位置，不是返回到匹配失败的下一个位置，这里都好理解，重点是求数组next。
                     这里只要j等于0，在next[j]赋值的之后，j就会等于-1；因为next[0]等于-1
                     */
                    j = next[j]; // j回到指定位置
                }
                if (j == needle.Length)
                    return i - j;
            }
            return -1;
        }

        private  void getNext(string p, int[] next)
        {
            //abcabb
            int len = p.Length;
            int i = 0;
            int j = -1;
            next[0] = -1;//这个默认的，
            /**
             * 匹配的时候是当前字符的前一个和前面的匹配，所以最后一个是不参与匹配的，可以看strStr方法的注释，
             */
            while (i < len - 1)
            {
                if (j == -1 || p[i] == p[j])
                {
                    /**
                     * 如果j不等于-1，指定的字符相等，那么i和j要往后移一位，这点很好理解，如果j为-1的时候，i往后移移位，j置为0
                     * 重新开始匹配。next[i]是匹配成功的数量
                     */
                    i++;
                    j++;
                    next[i] = j;
                }
                else
                    /**
                     * 关键是这里不好理解，为什么匹配失败要让next[j]等于j，要记住这里的next[j]是指匹配成功的数量，有可能为0，也有可能是其他数.比如
                     * 字符串ABCABXYABCABATDM,对应的next数组为{-1	0	0	0	1	2	0	0	1	2	3	4	5	1	0	0	}
                     */
                    j = next[j];
            }
        }
    }
}
